package 板子;
import java.util.Scanner;
public class 快速幂 {
	
	public static void main(String []args) {
		System.out.println(qmi(2,10));
		System.out.println(2 * 10 % 41);
		System.out.println(10 % 31);
		System.out.println(qmi(2,15));
	}
	
	/**
	 *		if((b & 1) == 1){ //如果k的二进制数的最后一位是 1。 比如1011 & 1 = 1
				res = (res * a) % mod;//取模， 防止结果溢出。
			}
			a = a * a % mod;//得到 a^1, a^2, a^4, a^8, .....
			b = b >> 1; //将b右移一位，去掉最低位。为了开始判断下一位。
		}
		
		
		这个 mod  是 对谁 进行  取余呢  ？？
	 * 
	 */
	public static int qmi(int a, int b){ //求 a^b
		int res = 1; // res保存结果
		while(b != 0){
			if((b & 1) == 1){ //如果k的二进制数的最后一位是 1。 比如1011 & 1 = 1
				res = (res * a);//取模， 防止结果溢出。 %mod
			}
			a = a * a ;//得到 a^1, a^2, a^4, a^8, .....  有个 % mod 
			b = b >> 1; //将b右移一位，去掉最低位。为了开始判断下一位。
		}
		return res;
	}


}
class _07_G_八次求和2 {
	static long mod = 123456789;
 
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		long n = in.nextLong();
		long ans = 0;
		for (long i = 1; i <= n; i++) {
			ans = (ans + quickPow(i, 8)) % mod;
		}
		System.out.println(ans);
		in.close();
//		System.out.println();
	}
 
	static long quickPow(long a, int b) {
		long ans = 1;
		while (b > 0) {
			if ((b & 1) == 1)
				ans = (ans * a) % mod;
			a = (a * a) % mod;
			b >>= 1;
		}
		return ans;
	}
	public static long f(long a,int b) {
		long ans =1L;
		while(b > 0) {
			if((b & 1) ==1) {
				ans = (ans * a) % mod;
			}
			a = (a * a) % mod;
			 b  >>= 1;
		}
		return  ans;
	}
}